#include <cstddef>
#include <unordered_set>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode *detectCycle(ListNode *head) {
  if (head == nullptr) {
    return nullptr;
  }
  unordered_set<ListNode *> set;
  while (head != nullptr) {
    if (set.count(head)) {
      return head;
    }
    set.insert(head);
    head = head->next;
  }
  return nullptr;
}
// 双指针解法
ListNode *detectCycle_(ListNode *head) {
  if (head == nullptr) {
    return nullptr;
  }
  ListNode *slow = head, *quick = head;
  do {
    for (int i = 0; i < 2; i++) {
      if (quick != nullptr) {
        quick = quick->next;
      }
    }
    if (slow != nullptr) {
      slow = slow->next;
    }
  } while (slow != quick);
  if (quick == nullptr) {
    return nullptr;
  }
  quick = head;
  while (slow != quick) {
    quick = quick->next;
    slow = slow->next;
  };
  return quick;
}